from collections import deque
from copy import deepcopy
from typing import List


class Solution:
    def flipChess(self, chessboard: List[str]) -> int:
        chessboard = [list(line) for line in chessboard]

        m, n = len(chessboard), len(chessboard[0])

        ans = 0

        for i0 in range(m):
            for j0 in range(n):
                # 判断(i0,j0)处是否能下黑子
                if chessboard[i0][j0] != ".":
                    continue

                change = 0

                # 遍历寻找能够翻转的位置
                now_board = deepcopy(chessboard)
                queue = deque([(i0, j0)])
                while queue:
                    i1, j1 = queue.popleft()

                    # 向上查找
                    eat = False
                    pos = []
                    i2 = i1 - 1
                    while i2 >= 0:
                        if now_board[i2][j1] == ".":
                            break
                        if now_board[i2][j1] == "X":
                            eat = True
                            break
                        else:
                            pos.append((i2, j1))
                        i2 -= 1
                    if eat:
                        for (i3, j3) in pos:
                            change += 1
                            now_board[i3][j3] = "X"
                            queue.append((i3, j3))

                    # 向下查找
                    eat = False
                    pos = []
                    i2 = i1 + 1
                    while i2 < m:
                        if now_board[i2][j1] == ".":
                            break
                        if now_board[i2][j1] == "X":
                            eat = True
                            break
                        else:
                            pos.append((i2, j1))
                        i2 += 1
                    if eat:
                        for (i3, j3) in pos:
                            change += 1
                            now_board[i3][j3] = "X"
                            queue.append((i3, j3))

                    # 向左查找
                    eat = False
                    pos = []
                    j2 = j1 - 1
                    while j2 >= 0:
                        if now_board[i1][j2] == ".":
                            break
                        if now_board[i1][j2] == "X":
                            eat = True
                            break
                        else:
                            pos.append((i1, j2))
                        j2 -= 1
                    if eat:
                        for (i3, j3) in pos:
                            change += 1
                            now_board[i3][j3] = "X"
                            queue.append((i3, j3))

                    # 向右查找
                    eat = False
                    pos = []
                    j2 = j1 + 1
                    while j2 < n:
                        if now_board[i1][j2] == ".":
                            break
                        if now_board[i1][j2] == "X":
                            eat = True
                            break
                        else:
                            pos.append((i1, j2))
                        j2 += 1
                    if eat:
                        for (i3, j3) in pos:
                            change += 1
                            now_board[i3][j3] = "X"
                            queue.append((i3, j3))

                    # 向左上查找
                    eat = False
                    pos = []
                    i2 = i1 - 1
                    j2 = j1 - 1
                    while i2 >= 0 and j2 >= 0:
                        if now_board[i2][j2] == ".":
                            break
                        if now_board[i2][j2] == "X":
                            eat = True
                            break
                        else:
                            pos.append((i2, j2))
                        i2 -= 1
                        j2 -= 1
                    if eat:
                        for (i3, j3) in pos:
                            change += 1
                            now_board[i3][j3] = "X"
                            queue.append((i3, j3))

                    # 向右上查找
                    eat = False
                    pos = []
                    i2 = i1 - 1
                    j2 = j1 + 1
                    while i2 >= 0 and j2 < n:
                        if now_board[i2][j2] == ".":
                            break
                        if now_board[i2][j2] == "X":
                            eat = True
                            break
                        else:
                            pos.append((i2, j2))
                        i2 -= 1
                        j2 += 1
                    if eat:
                        for (i3, j3) in pos:
                            change += 1
                            now_board[i3][j3] = "X"
                            queue.append((i3, j3))

                    # 向左下查找
                    eat = False
                    pos = []
                    i2 = i1 + 1
                    j2 = j1 - 1
                    while i2 < m and j2 >= 0:
                        if now_board[i2][j2] == ".":
                            break
                        if now_board[i2][j2] == "X":
                            eat = True
                            break
                        else:
                            pos.append((i2, j2))
                        i2 += 1
                        j2 -= 1
                    if eat:
                        for (i3, j3) in pos:
                            change += 1
                            now_board[i3][j3] = "X"
                            queue.append((i3, j3))

                    # 向右下查找
                    eat = False
                    pos = []
                    i2 = i1 + 1
                    j2 = j1 + 1
                    while i2 < m and j2 < n:
                        if now_board[i2][j2] == ".":
                            break
                        if now_board[i2][j2] == "X":
                            eat = True
                            break
                        else:
                            pos.append((i2, j2))
                        i2 += 1
                        j2 += 1
                    if eat:
                        for (i3, j3) in pos:
                            change += 1
                            now_board[i3][j3] = "X"
                            queue.append((i3, j3))

                ans = max(ans, change)

        return ans


if __name__ == "__main__":
    # 3
    print(Solution().flipChess(chessboard=["....X.",
                                           "....X.",
                                           "XOOO..",
                                           "......",
                                           "......"]))

    # 2
    print(Solution().flipChess(chessboard=[".X.",
                                           ".O.",
                                           "XO."]))

    # 4
    print(Solution().flipChess(chessboard=[".......",
                                           ".......",
                                           ".......",
                                           "X......",
                                           ".O.....",
                                           "..O....",
                                           "....OOX"]))
